1. Field of the Invention
This invention relates to the field of image processing and pattern matching, and in particular to the comparison of two datasets based on a histogram characterization of each of the two datasets.
2. Description of Related Art
Histograms are commonly used to characterize sets of data. Similarities between sets of data can often be determined by comparing the relative frequency of occurrence of common values in each of the sets of data. Pattern matching, and in particular image matching, often includes histogram comparisons to determine similarities between images, or to search for target objects within larger images.
A histogram comprises ‘classes’, or ‘bins’, for containing a frequency count of the number of members of the class within the dataset being characterized. Each data item is associated with a class, based on its value, and the occurrence of each data value in the dataset causes the frequency count of the associated class to be incremented. In some histogram structures, each data item may be associated with multiple classes, and the frequency count of each class is incremented for each occurrence of the data item. For ease of reference herein, each data value is assumed to be associated with a single class, without loss of generality, because the principles of this invention are applicable regardless of the techniques used to assign frequency counts to classes.
The number of classes used to classify the different data values of a dataset generally determines the discriminating capability, or resolution, of the histogram. If many different data values are assigned to the same histogram class, the histograms of datasets having substantially different data values may be equivalent, and therefore indistinguishable. Conversely, if each different data value is assigned to a different histogram class, the histograms of datasets having very similar, but not exactly the same, data values will be substantially different, even though the datasets are similar. Generally, the number of classes used to classify the different data values is selected to provide a good distinguishing capability among substantially different datasets while also providing similar or equivalent histograms for substantially similar datasets.
In a conventional histogram comparison process, the time required to provide a measure of similarity between histograms is proportional to the number of classes in the histograms, and the time to compute the histogram of an area is proportional to the size of the area. A histogram structure that has good distinguishing capability (i.e. a large number of classes) may result in an excessively long processing time. In some applications, such as real-time video processing, the speed of processing is crucial to the feasibility of the application, and compromises that reduce the distinguishing capabilities of the histogram are often imposed.
A common application in the field of image processing is a search of a relatively large image for the location of a relatively small target image. In such an application, each region of the larger image that could possibly contain the smaller target image is assessed to determine whether the content of the region corresponds to the target content. In the context of this application, a histogram is created for the content of the target, and this target histogram is compared to a histogram corresponding to each of the possible target-containing regions in the larger image. Consider an image that is N by M pixels in size, and a target that is n by m pixels in size. The image comprises (N−(n−1))×(M−(m−1)) regions that could contain the target. In a typical application, an image may be 1024×1024 pixels in size, and a target may be less than 100×100 pixels in size. In this example, the image comprises almost a million possible regions, and a histogram is required for each of these regions. This potentially large number of regions to evaluate further necessitates an efficient histogram creation and histogram comparison process, particularly for real-time image processing.